1092E - Minimal Diameter Forest - CodeForces Solution

#include<bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <iterator>
#include <bitset>
#include <assert.h>
#include <new>
#include <sstream>
#include <time.h>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef     long long    ll;
typedef     unsigned long long    ull;
typedef     vector<int> vi;
typedef     vector<long long> vl;
typedef     pair<int, int>pi;
typedef     pair<long long, long long>pl;
#define F   first
#define S   second
#define pb  push_back
#define     all(x)      x.begin() , x.end()
#define       FOR(i,a,b) for(i=a;i<=b;i++)
#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)
#define setpr(x) cout<<setprecision(x)<<fixed
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
template <typename T> inline void Int(T &a) {
	bool minus = false; a = 0; char ch = getchar();
	while (true) { if (ch == '-' or (ch >= '0' && ch <= '9')) break; ch = getchar(); }
	if (ch == '-') minus = true; else a = ch - '0';
	while (true) { ch = getchar(); if (ch < '0' || ch > '9') break; a = a * 10 + (ch - '0'); }
	if (minus)a *= -1 ;
}
#ifdef LOCAL
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl ;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << ' ' ;
	err(++it, args...);
}
#else
#define error(args...)
#endif

const int N          = (int)1003 ;
const int maxN       = (int)1e6 + 6 ;
const ll  Mod        = (ll)1e9 + 7 ;
const int inf        = (int)2e9 ;
const ll  Inf        = (ll)1e18 ;
const int mod        = (int)1e9 + 7 ;
const double EPS     = (double)1e-9 ;
const double PI      = (double)acos(-1.0) ;


inline int add(int a, int b, int mod) {a += b ; return a >= mod ? a - mod : a ;}
inline int sub(int a, int b, int mod) {a -= b ; return a < 0 ? a + mod : a ;}
inline int mul(int a, int b, int mod) {return (ll)a * b % mod ;}
vector<ll>vt;
vector<ll>g[N + 3];
ll dis1[N + 3], dis2[N + 3];
ll node1, node2, mx = -1;
ll vis[N + 3];
void dfs(ll node, ll p, ll d) {
	vis[node] = 1;
	if (d >= mx) {
		mx = d;
		node1 = node;
	}
	for (ll x : g[node]) {
		if (x == p) continue;
		dfs(x, node, d + 1);
	}
}
void dfs1(ll node, ll p, ll d) {
	dis1[node] = d;
	if (d >= mx) {
		mx = d;
		node2 = node;
	}
	for (ll x : g[node]) {
		if (x == p) continue;
		dfs1(x, node, d + 1);
	}
}
void dfs2(ll node, ll p, ll d) {
	dis2[node] = d;
	for (ll x : g[node]) {
		if (x == p) continue;
		dfs2(x, node, d + 1);
	}
}
ll mx_d = -1, mn_nd = 0, dis_nd = 1e18;
void dfs3(ll node, ll p) {
	ll x = max(dis1[node], dis2[node]);
	if (dis_nd >= x) {
		dis_nd = x;
		mn_nd = node;
	}
	for (ll x : g[node]) {
		if (x == p) continue;
		dfs3(x, node);
	}
}
int main() {
	int test = 1, fac = 1;
	// cin>>test;
	while (test--) {
		ll n, i, j, x, y, m;
		cin >> n >> m;
		for (i = 1; i <= m; i++) {
			cin >> x >> y;
			g[x].pb(y);
			g[y].pb(x);
		}
		vector<pl> v;
		ll dd = 0;
		for (i = 1; i <= n; i++) {
			if (vis[i]) continue;
			mx = -1;
			mx_d = -1;
			dfs(i, 0, 0);
			mx = -1;
			dfs1(node1, 0, 0);
			dfs2(node2, 0, 0);
			dis_nd = 1e18;
			//error(i,node1,node2)
			dd = max({dd, dis1[node2], dis2[node1]});
			dfs3(node1, 0);
			//error(dis_nd,mn_nd)
			v.pb({dis_nd, mn_nd});
		}
		ll sz = v.size();
		sort(v.rbegin(), v.rend());
		if (sz == 1) {
			cout << dd << endl;
			return 0;
		}
		vector<pl>res;
		for (i = 1; i < v.size(); i++) {
			g[v[0].S].pb(v[i].S);
			g[v[i].S].pb(v[0].S);
			res.pb({v[0].S,v[i].S});
		}
		mx=-1;
		dfs(1,0,0);
		mx=-1;
		dfs1(node1,0,0);
		cout<<mx<<endl;
		for(pl p:res) cout<<p.F<<" "<<p.S<<endl;
	}
	return 0;
}